package tree.structure.dicttree;

import java.util.Arrays;

/**
 * @author: 26233
 * @create: 2022-08-02 18:11:58
 * @Description
 *
 * 字典树：字符串以树的形式存储的结构
 *
 **/

public class DictTree {

    private DictTreeNode root;

    public DictTree() {
        root = new DictTreeNode();
    }

    public void insert(String input) {
        insert(input, 0, root);
    }
    public void insert(String input, int index, DictTreeNode curNode) {

        if (index >= input.length()) {
            return;
        }

        assert input.charAt(index) >= 'a' && input.charAt(index) <= 'z';
        int charIndex = (input.charAt(index) - 'a');
        if (curNode.getNextNodes() == null) {
            curNode.setNextNodes(new DictTreeNode[26]);
        }

        if (curNode.getNextNodes()[charIndex] == null) {
            curNode.getNextNodes()[charIndex] = new DictTreeNode();
            curNode.getNextNodes()[charIndex].setV(input.charAt(index));
        }

        if (index == input.length() - 1) {
            curNode.getNextNodes()[charIndex].setTail(true);
            return;
        }

        insert(input, index + 1, curNode.getNextNodes()[charIndex]);
    }

    public boolean find(String s) {
        DictTreeNode tempNode = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int index = c - 'a';
            if (tempNode == null || tempNode.getNextNodes()[index] == null) {
                return false;
            }
            if (tempNode.getNextNodes()[index] != null && tempNode.getNextNodes()[index].getV() != c) {
                return false;
            }
            if (i == s.length() - 1 && tempNode.getNextNodes()[index].isTail()) {
                return true;
            }
            tempNode = tempNode.getNextNodes()[index];
        }
        return false;
    }

    public static void main(String[] args) {

        String[] input = {"abc","ab","ac","bc","abcd","c",};
        DictTree dictTree = new DictTree();
        Arrays.stream(input).forEach(dictTree::insert);

        boolean abc = dictTree.find("abc");
        System.out.println("abc = " + abc);

        System.out.println("dictTree = " + dictTree);

    }
}
